"""
611. 有效三角形的个数
中等
相关标签
premium lock icon
相关企业
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

 

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4
 

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
"""
from typing import List

# 未做出
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        """
        双指针
        :param nums:
        :return:
        """
        nums.sort()
        ans = 0
        for i in range(2,len(nums)):
            l = 0
            r = i - 1
            c = nums[i]
            while l<i-1:
                print(f"l:{l},r:{r},i:{i}")
                if nums[l] + nums[r]> c:
                    #遍历右边，每次找到能组成三角形的最小左边，然后r-l就是此时该右边和左边能和i组能的数量.
                    ans += r - l
                    #当前节点r已经找完
                    r -=1
                else:
                    #增大l，往右边找
                    l+=1
        return ans

    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        for k in range(2, len(nums)):
            c = nums[k]
            i = 0  # a=nums[i]
            j = k - 1  # b=nums[j]
            while i < j:
                if nums[i] + nums[j] > c:
                    # 由于 nums 已经从小到大排序
                    # nums[i]+nums[j] > c 同时意味着：
                    # nums[i+1]+nums[j] > c
                    # nums[i+2]+nums[j] > c
                    # ...
                    # nums[j-1]+nums[j] > c
                    # 从 i 到 j-1 一共 j-i 个
                    ans += j - i
                    j -= 1
                else:
                    # 由于 nums 已经从小到大排序
                    # nums[i]+nums[j] <= c 同时意味着
                    # nums[i]+nums[j-1] <= c
                    # ...
                    # nums[i]+nums[i+1] <= c
                    # 所以在后续的内层循环中，nums[i] 不可能作为三角形的边长，没有用了
                    i += 1
        return ans

if __name__ == '__main__':
    print(Solution().triangleNumber([2,2,3,4]))


